Search results for "Range query"
showing 3 items of 3 documents
Hyperion
2019
Indexes are essential in data management systems to increase the speed of data retrievals. Widespread data structures to provide fast and memory-efficient indexes are prefix tries. Implementations like Judy, ART, or HOT optimize their internal alignments for cache and vector unit efficiency. While these measures usually improve the performance substantially, they can have a negative impact on memory efficiency. In this paper we present Hyperion, a trie-based main-memory key-value store achieving extreme space efficiency. In contrast to other data structures, Hyperion does not depend on CPU vector units, but scans the data structure linearly. Combined with a custom memory allocator, Hyperion…
A Two-layer Partitioning for Non-point Spatial Data
2021
Non-point spatial objects (e.g., polygons, linestrings, etc.) are ubiquitous and their effective management is always timely. We study the problem of indexing non-point objects in memory. We propose a secondary partitioning technique for space-oriented partitioning indices (e.g., grids), which improves their performance significantly, by avoiding the generation and elimination of duplicate results. Our approach is novel and of a high impact, as (i) it is extremely easy to implement and (ii) it can be used by any space-partitioning index. We show how our approach can be used to boost the performance of spatial range queries. We also show how we can avoid performing the expensive refinement s…
A data aggregation strategy based on wavelet for the internet of things
2017
The advent of emerging information and communication technologies, such as RFID, small size sensors and sensor networks, has made accessible a huge amount of information that requires sophisticated and efficient search algorithms to support queries on that data. In this paper we focus on the problem of aggregating data collected from these devices to efficiently support queries, inferences or statistics on them. In general, data aggregation techniques are necessary to efficiently collect information in a compact and cost-effective way. Some current solutions try to meet the above criteria, by exploiting different data aggregation techniques, for instance BitVector or Q_Digest. In this manus…